#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

 

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/gas-station
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

///这个暴力代码这么垃圾一看就是我写的
int getNextPos(vector<int> &gas, int nowPos) {
    if (nowPos + 1 < gas.size())
        return nowPos + 1;
    else if (nowPos + 1 == gas.size()) {
        return 0;
    }

    return -1;
}

//直接暴力一下
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

    for (int i = 0; i <gas.size() ; ++i) {

        int startIndex=i;
        int nextIndex=getNextPos(gas,i);
        int temp=gas[i];;
        int nowIndex=i;
        while (startIndex!=nextIndex){
            temp=temp-cost[nowIndex];//《=
            nowIndex=nextIndex;
            if (temp<0)
                break;
            temp+=gas[nextIndex];
            //否则
            nextIndex= getNextPos(gas,nextIndex);
        }
        if (startIndex == nextIndex && temp >= 0) {
            temp = temp - cost[nowIndex];//《=
            if (temp >= 0)
                return startIndex;
        }

    }
    return -1;
}

/*
 * 一个例子让你醍醐灌顶！

思想：计算油量总亏损，总亏损的后一个点就是起点，可以这么想，我们要在前面留下尽可能多的油给后的亏损的大户用。

力扣里的测试用例，gas = [5,1,2,3,4],cost = [4,4,1,5,1]。

从0开始 对应位置相减可以算的本站的剩余油量情况。 得到剩余油量数组 temp = [1,-3,1,-2,3]。 将剩余油量相加，到下标3时的总亏损最多，为 -3。 所以要从4号开始前面累计足够多的油给下标为3时，即总亏损最多的加油站用。

能用这种逻辑的条件就是题目所给的：如有答案，则保证答案唯一。
 *
 *
 *
TODO 其实怎么说就是从那个算下来结果最小的位置出发 ,因为平时路上在积累油
 *
 * **/

//抄的
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    //获取min
    int min = INT_MAX;//寻找一个欠油量的最小值
    int cursum = 0;
    for (int i = 0; i < gas.size(); ++i) {
        int rest = gas[i] - cost[i];
        cursum += rest;
        if (cursum < min)
            min = cursum;

    }
    //
    if (cursum < 0)
        return -1;//花费和油量加起来怎么也得>=0

    if (min >= 0)
        return 0;//说明从哪走都OK 油没有断过

    //否则从后面出发找到能抵消这个空缺油量的


    for (int i = gas.size() - 1; i >= 0; --i) {
        int sum_ = gas[i] - cost[i];
        min = min + sum_;
        if (min >= 0)
            return i;


    }

    return -1;


}

//第二种
//int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
//    int curSum = 0;
//    int totalSum = 0;
//    int start = 0;
//    for (int i = 0; i < gas.size(); i++) {
//        curSum += gas[i] - cost[i];
//        totalSum += gas[i] - cost[i];
//        if (curSum < 0) {   // 当前累加rest[i]和 curSum一旦小于0
//            start = i + 1;  // 起始位置更新为i+1
//            curSum = 0;     // curSum从0开始
//        }
//    }
//    if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
//    return start;
//}
